package com.rui.study.algorithm.learn_栈数组栈;

/**
 * @program: study_20180903
 * @description: 栈。基于数组实现的栈，线程不安全，自动扩容。
 * 复杂度分析：push的最好情况时间复杂度为O(1)，最坏情况时间复杂度为O(n)。
 * 均摊时间复杂度，摊还分析n-1个O(1)，1个O(n)，因此，均摊时间复杂度O(1)。
 * @author: Yaowr
 * @create: 2018-10-24 08:36
 **/
public class Stack<T> {

    private int head;

    private Object[] array;

    public Stack() {
        this.array = new Object[16];
        head = 0;
    }

    public boolean push(T t) {
        if (head == array.length) {
//            return false;
            Object[] newArray = new Object[2 * array.length];
            for (int i = 0; i < array.length; i++) {
                newArray[i] = array[i];
            }
            array = newArray;   // 指向新的数组
        }
        array[head++] = t;
        return true;
    }

    public T pop() {
        if (head == 0) {
            return null;
        }
        return (T)array[--head];
    }

    public int size() {
        return head;
    }
}
